/*
 * TBX: ToolBoX of Simgrid : some convenient tools (FIFO lists, hash
 * tables, graphs,...)  Copyright (C) 2002 "the MSG Team" (see AUTHORS
 * file).
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation; either version 2, or (at
 * your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
 * USA.
 */

#ifndef TBX_GRAPH_H
#define TBX_GRAPH_H

#include <stdlib.h>
#include "tbx_fifo.h"
#include "tbx_hashtable.h"
#include "tbx_macros.h"

#define VERY_SHORT_INT unsigned char

/* Node structure */
typedef struct TBX_Node {
  char *name;
  TBX_FIFO_t out;
  TBX_FIFO_t in;
  int index;
  int interf_index;
  int interfCount_index;
  int slice_index;
  struct TBX_Node *leader;
  struct TBX_Node *separator;
  int interfering;
  int special;
  void *data;
} *TBX_Node_t;

/* Edge structure */
typedef struct TBX_Edge {
  char *name;
  TBX_Node_t src;
  TBX_Node_t dst;
  long double distance;
  void *data;
} *TBX_Edge_t;

/* Graph structure */
typedef struct TBX_Graph {
  char *name;
  TBX_HashTable_t nodes;
  TBX_HashTable_t edges;
  unsigned short int directed;
  int node_count;
  TBX_Node_t *node_table;
  int node_table_count;
  void *data;
  TBX_Node_t *route;
} *TBX_Graph_t;

typedef struct TBX_InterfTable {
  int host_table_count;
  TBX_Node_t *host_table;
  VERY_SHORT_INT *interf;
} *TBX_InterfTable_t;

typedef struct TBX_InterfTableCount {
  int host_table_count;
  TBX_Node_t *host_table;
  int *interf_count;
  int max_interference;
} *TBX_InterfTableCount_t;

typedef struct TBX_SliceTable {
  int host_table_count;
  TBX_Node_t *host_table;
  VERY_SHORT_INT *slice;
} *TBX_SliceTable_t;
 
/* API */
TBX_Graph_t TBX_Graph_newGraph(const char *name, unsigned short int directed,
			       void *data);
TBX_Node_t TBX_Graph_newNode(TBX_Graph_t g,const char *name, void *data);
TBX_Edge_t TBX_Graph_newEdge(TBX_Graph_t g,const char *name,
			     TBX_Node_t src, TBX_Node_t dst, void *data);

void TBX_Graph_freeNode(TBX_Graph_t g, TBX_Node_t n, void free_function(void * ptr));
void TBX_Graph_freeEdge(TBX_Graph_t g, TBX_Edge_t e, void free_function(void * ptr));
void TBX_Graph_freeGraph(TBX_Graph_t g, 
			 void node_free_function(void * ptr),
			 void edge_free_function(void * ptr),
			 void graph_free_function(void * ptr));

TBX_Node_t TBX_Graph_nodeSearch(TBX_Graph_t g,const char *name);

void TBX_Graph_exportToGraphViz(TBX_Graph_t g, const char *filename);
void TBX_Graph_fixNodeNumbering(TBX_Graph_t g);

/* void *TBX_Graph_graphToArray(TBX_Graph_t g); */
void TBX_Graph_FloydWarshall(TBX_Graph_t g);
#define ROUTE(g,a,b) ((g)->route)[((a)->index)*((g)->node_count) + ((b)->index)]

/**************** Interferences **************/

TBX_InterfTable_t TBX_Graph_newInterfTable(TBX_FIFO_t host_list);
void TBX_Graph_graphInterfTableInit(TBX_Graph_t g,TBX_InterfTable_t table);
void TBX_Graph_freeInterfTable(TBX_InterfTable_t table);
void TBX_Graph_interferenceTableDump (TBX_InterfTable_t table);
void TBX_Graph_interferenceTableSave (TBX_InterfTable_t table, const char *filename);
int TBX_Graph_interferenceTableRead (const char *filename,
				     /*OUT*/ TBX_Graph_t *graph,
				     /*OUT*/ TBX_InterfTable_t *interf,
				     /*OUT*/ TBX_FIFO_t *hlist);

#define INTERFERENCE(table,a,u,b,v) \
           (table)->interf[(a)->interf_index*(table)->host_table_count*(table)->host_table_count*(table)->host_table_count + \
                          (u)->interf_index*(table)->host_table_count*(table)->host_table_count + \
                          (b)->interf_index*(table)->host_table_count + \
                          (v)->interf_index]

TBX_SliceTable_t TBX_Graph_newSliceTable(TBX_FIFO_t host_list);
void TBX_Graph_graphSliceTableInit(TBX_SliceTable_t table);
void TBX_Graph_freeSliceTable(TBX_SliceTable_t table);
#define SLICE(slicetable,a,b) \
             (slicetable)->slice[((a)->slice_index)*((slicetable)->host_table_count) + \
                                 (b)->slice_index]

TBX_InterfTableCount_t TBX_Graph_newInterfTableCount(TBX_FIFO_t host_list);
void TBX_Graph_freeInterfTableCount(TBX_InterfTableCount_t table);
void TBX_Graph_graphInterfTableCountInit(TBX_InterfTableCount_t table);
#define INTERFERENCE_COUNT(tableCount,a,b) \
           (tableCount)->interf_count[(a)->interfCount_index*(tableCount)->host_table_count + \
                                      (b)->interfCount_index]


TBX_InterfTable_t TBX_Graph_buildInterferences(TBX_Graph_t g, TBX_FIFO_t host_list);
TBX_InterfTableCount_t TBX_Graph_countInterferences(TBX_FIFO_t host_list, 
						    TBX_InterfTable_t table);
TBX_SliceTable_t TBX_Graph_getSlice(TBX_FIFO_t to_explore, TBX_InterfTable_t table,
				    TBX_Node_t n_a, TBX_Node_t n_b);

TBX_Graph_t TBX_Graph_exploreInterference(TBX_InterfTable_t interf);

static __INLINE__ void * TBX_Graph_getNodeData(TBX_Node_t n) 
{
  ASSERT((n!=NULL),"Invalide node!");
  return n->data;
}
static __INLINE__ void * TBX_Graph_getEdgeData(TBX_Edge_t n) 
{
  ASSERT((n!=NULL),"Invalide node!");
  return n->data;
}
static __INLINE__ void * TBX_Graph_getGraphData(TBX_Graph_t n) 
{
  ASSERT((n!=NULL),"Invalide node!");
  return n->data;
}

/** Convenient for loop : g is a graph, n a node, e an edge, b a bucket and i an item **/
#define TBX_Graph_foreachNode(g,n,b) for(b=TBX_HashTable_getFirstBucket((g)->nodes);   \
					    ((b)?(n=(TBX_Node_t)(b->content)):(NULL)); \
					  b=TBX_HashTable_getNextBucket((g)->nodes,b))
#define TBX_Graph_foreachEdge(g,e,b) for(b=TBX_HashTable_getFirstBucket((g)->edges);   \
					    ((b)?(e=(b->content)):(NULL));             \
					  b=TBX_HashTable_getNextBucket((g)->edges,b))
#define TBX_Graph_foreachInNeighbor(v,n,i)            \
   for(i=TBX_FIFO_getFirstItem((v)->in);              \
     ((i)?(n=((TBX_Edge_t)(i->content))->src):(NULL));\
       i=TBX_FIFO_getNextItem(i))
#define TBX_Graph_foreachOutNeighbor(v,n,i)           \
   for(i=TBX_FIFO_getFirstItem((v)->out);             \
     ((i)?(n=((TBX_Edge_t)(i->content))->dst):(NULL));\
       i=TBX_FIFO_getNextItem(i))

#endif
